package org.example.method;

import org.example.graph.Edge;
import org.example.graph.Vertex;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


public class TopologicalSortDFS {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("网页基础");
        Vertex v2 = new Vertex("Java基础");
        Vertex v3 = new Vertex("javaWeb");
        Vertex v4 = new Vertex("Spring框架");
        Vertex v5 = new Vertex("微服务框架");
        Vertex v6 = new Vertex("数据库");
        Vertex v7 = new Vertex("实战项目");

        v1.edges = List.of(new Edge(v3));
        v2.edges = List.of(new Edge(v3));
        v3.edges = List.of(new Edge(v4));
        v6.edges = List.of(new Edge(v4));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of(new Edge(v7));
        v7.edges = List.of(new Edge(v5));

        List<Vertex> graph = new ArrayList<>(List.of(v1, v2, v3, v4, v5, v6, v7));
        //1.统计每个顶点的入度
        for (Vertex vertex : graph) {
            for (Edge edge : vertex.edges) {
                edge.linked.inDegree++;
            }
        }
        //2.将入度为0的节点压入栈
        LinkedList<Vertex> queue = new LinkedList<>();
        for (Vertex vertex : graph) {
            if (vertex.inDegree == 0) {
                queue.add(vertex);
            }
        }
        //3.对每个入度为0的节点进行深度优先遍历
        LinkedList<String> stack = new LinkedList<>();
        for (Vertex vertex : queue) {
            dfs(vertex,stack);
        }
        System.out.println(stack);
    }

    public static void dfs(Vertex vertex, LinkedList<String> stack) {
        if (vertex.status == 2){
            return;
        }
        if (vertex.status == 1){
            throw new RuntimeException("发现环");
        }
        vertex.status = 1;
        for (Edge edge : vertex.edges) {
            dfs(edge.linked,stack);
        }
        vertex.status = 2;
        stack.push(vertex.getName());
    }

}
